package com.su.test;

import java.util.Arrays;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.LinkedBlockingQueue;


//宽度优先搜索，最高可达17步
public class BFS extends Strategy{


    @Override
    public void run() {

        super.steps = 0;
        //open表
        Queue<Node> openQueue = new LinkedBlockingQueue<>();

        int emptyIndex=0;     //记录空格的位置
        for (int i = 0; i < length; i++) {
            if(initArr[i] == 0){
                emptyIndex = i;
                break;
            }

        }
        Node initNode = new Node(initArr,emptyIndex,null);
        openQueue.add(initNode);
        //close表
        Set<Node> closeSet = new TreeSet<>();

        while (!openQueue.isEmpty()){
            super.steps++;      //记录步数

            Node curNode = openQueue.poll();

            //当前节点是目标节点
            if(Arrays.equals(curNode.num,targetArr)){
                super.lastNode = curNode;
                return;
            }

            int emptyIndexOfCur = curNode.emptyIndex;   //当前节点空格位置

            //左移
            if(emptyIndexOfCur % this.col > 0){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,-1);
                Node nextNode = new Node(nextArr,emptyIndexOfCur-1, curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //上移
            if(emptyIndexOfCur > this.col){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,-this.col);

                Node nextNode = new Node(nextArr,emptyIndexOfCur-this.col, curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //右移
            if(emptyIndexOfCur % this.col < this.col - 1){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,1);
                Node nextNode = new Node(nextArr,emptyIndexOfCur + 1, curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //下移
            if (emptyIndexOfCur < length - this.col){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,this.col);
                Node nextNode = new Node(nextArr,emptyIndexOfCur + this.col, curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }

            closeSet.add(curNode);

        }
    }
}
/*
输入初始数组、目标数组
创建两个表，OPEN表保存所有已生成而未考察的节点，
CLOSED表中记录已访问过的节点。将起点放入OPEN表。
while(open != NULL) {
    从open表中队首节点n
    if(节点n == 目标节点){
        创建一个List,用来保存最佳路线的数组（表示八数码）
        while(节点n != NULL){
            将节点n的数组添加至List
            节点n = 节点n->parent
        }
        倒序输出List
    }
     for(当前节点n的每一个子节点X){
         if(子节点X not in Closed表)
            将子节点X加入Open表中
     }
     将当前节点n加入到Closed表中
}



 */
